package vip.zhenzicheng.algorithm.leetcode.stack_queue;

/**
 * <a href="https://leetcode.cn/problems/daily-temperatures/">每日温度 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-23 19:32
 */
public class DailyTemperatures_739 {

  /*使用单调栈解决，规定靠近栈顶的为最小，栈底为最大*/
  // public int[] dailyTemperatures(int[] temperatures) {
  //   Deque<Integer> stack = new LinkedList<>(); // 栈
  //   int[] res = new int[temperatures.length];
  //
  //   for (int i = 0; i < temperatures.length; i++) {
  //     // 比栈顶（最小值）大，一直出栈代表处理之前的元素了
  //     while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
  //       int idx = stack.pop(); // 或者使用poll()
  //       res[idx] = i - idx;
  //     }
  //     stack.push(i);
  //   }
  //   return res;
  // }

  /*反向遍历数组，优化版暴力枚举，利用之前的结果*/
  public int[] dailyTemperatures(int[] temperatures) {
    int len = temperatures.length;
    int[] res = new int[len];
    res[len - 1] = 0; // 最后一个

    for (int i = len - 2; i >= 0; i--) { // 从倒数第二个倒着找
      for (int backIdx = i + 1; backIdx < len; backIdx = backIdx + res[backIdx]) { // 从当前数的下一位开始往后找，每次往后找的过程中利用之前结果，跳过重复判断的元素
        if (temperatures[i] < temperatures[backIdx]) {
          res[i] = backIdx - i; // 距离
          break;
        } else if (res[backIdx] == 0) { // 当结果数组为0的时候还没找到，就代表后面一定没有更大
          res[i] = 0;
          break;
        }
      }
    }
    return res;
  }

}
